Digital halftoning reduces the number of pixel levels used to represent an image to a smaller number of pixel levels that can actually be displayed by a real display device. For example, 24 bits are commonly used to represent the color information for each pixel of a color image, 8 bits each for the primary colors red, green, and blue. To print such images on a binary, 3 primary color, ink-jet printer, the 24-bit red, green, and blue, information is first converted to 24 bits of cyan, magenta, and yellow information, 8 bits each for cyan, magenta, and yellow, by techniques familiar to persons skilled in the art. Eight bits specify 256 levels of colorant for each of these printable primaries.
A binary ink-jet printer, however, can print only 2 levels of each colorant at each pixel location. A halftoning algorithm is therefore employed to make the decision to print or to not print a dot of each of the primaries at each pixel location, given the original 256 levels of information for each primary. The resulting information then consists of three planes of dot information, corresponding to pixel locations at which cyan, magenta, and yellow dots are to be placed.
Though binary printers can represent only two levels of information at a given pixel location, halftoning algorithms produce patterns of dots over wide areas to simulate the appearance of a much larger number of shades. Therefore, if a solid color is to be produced over a wide area, a noticeable pattern of dots may be used to represent the color. The degree to which the pattern is noticeable is governed by, among other things, the contrast ratio between the color of the dots themselves and the color that surrounds them. The contrast ratio is the ratio of the darkness of the dots to the darkness of the color which surrounds them. The bigger the difference, the more noticeable the dots. For similar patterns of black and yellow dots printed on white paper, the pattern of black dots will be more noticeable than the pattern of yellow dots since black is much darker than white, and yellow is only slightly darker than white.
Two main objectives of a halftoning algorithm are 1) to make good decisions that result in pleasing patterns of dots, and 2) to make quick decisions, since the number of pixels used to represent an image is typically very large. There are two general classes of halftoning algorithms that each meet just one of these goals. Error diffusion produces pleasing patterns of dots, but as will be shown requires much processing time. On the other hand, ordered dither produces patterns with objectionable artifacts, but requires less processing time than error diffusion. The properties of these algorithms and how they work are described below.
Error diffusion, as described by Robert Floyd and Louis Steinberg in "An Adaptive Algorithm for Spatial Grayscale", 1975 SID International Symposium, Digest of Technical Papers, pp. 36-37, gets its name since it involves the computation of the error between the original 8-bit value represented by the original image data and the binary pixel value chosen as output at a given pixel location, and spreads or diffuses this error to neighboring pixel locations.
Consider the binarization of an 8-bit cyan dot plane of image information, in order that the image can be printed on a binary ink-jet printer. Error diffusion is also performed in the prior art on magenta, yellow, and optionally a black dot plane in the same manner as for the cyan plane, according to FIG. 1. We will use the convention in this document that the minimum colorant value represented by 8 bits, 0, represents the lightest shade, white, of a particular colorant, and the maximum value, 255, represents the darkest shade of the colorant, and all values between 0 and 255 represent shades between the lightest and darkest shades of the colorant.
A binary printer can elect to either print or not print a dot at each pixel location, corresponding only to the darkest and lightest shades, respectively, represented by the original 8-bit colorant values. If an 8-bit cyan colorant value, C, is either 0 or 255, a binary printer can faithfully represent this value by either not printing or printing, respectively, a dot of cyan ink at the corresponding pixel location. If C is other than 0 or 255, the error diffusion algorithm must decide whether or not to print a dot of cyan ink.
This is done by comparing C with a threshold value, preferably 127.5, the midpoint of 0 and 255. If C is greater than this threshold, a cyan dot is printed. Though the original intent was to produce a cyan shade C, effectively, by printing a dot, a cyan value of 255 was printed. An error E between the intended value and the actual value defined as E=C-255 is therefore generated at the given pixel location. If C is less than the threshold, a cyan dot is not printed. Though the original intent was to produce a cyan shade C, effectively, by not printing a dot, a cyan value of 0 was printed. An error E between the intended value and the actual value defined as E=C is therefore generated at the given pixel location.
According to the method of error diffusion, the error E is diffused to neighboring pixels that have not yet been binarized, thereby modifying their colorant values. The error generated at a pixel location (x, y) is therefore added to neighboring 8-bit pixel values according to the following weights proposed by Floyd and Steinberg: E*7/16 to location (x+1, y), E*1/16 to location (x-1, y+1), E*5/16 to location (x, y+1), and E*3/16 to location (x+1, y+1). Other weights have been proposed. Diffusing the error to only one position results in faster computation, but the quality of the output dot pattern is generally unacceptable.
If a dot is printed at a pixel location (x, y) where C is less than 255, negative values will be added to neighboring pixel locations, decreasing their probability of being printed, thereby compensating for overprinting at location (x, y). If a dot is not printed at a pixel location (x, y) where C is greater than 0, positive values will be added to neighboring pixel locations, increasing their probability of being printed, thereby compensating for underprinting at location (x, y).
After binarizing a given pixel at location (x, y) and diffusing error to neighboring pixels, the error diffusion algorithm proceeds to the binarization of the next, horizontally adjacent, pixel. It has been proposed that to produce pleasing patterns of dots the direction of processing alternate between rasters.
Error diffusion has also been extended to devices that produce multiple levels of a given colorant. Such devices are capable of printing, for example, three levels of a given colorant, none, light, or dark, instead of just two levels, on or off. Whereas not printing a dot may be equivalent to printing a colorant value 0, and printing a dark dot may be equivalent to printing a colorant value 255, printing a light dot may be equivalent to printing a colorant value 128. When choosing which of the three levels of colorant to print, the level closest to the original image colorant value is chosen, and the error is defined as E=original colorant value--effective level of printed dot. The resulting image information then consists of multiple dot planes, or patterns of dots for each colorant.
The error diffusion halftoning technique described above has been found to produce random looking, pleasing patterns of dots. However, due to the multiple steps of comparing against a threshold, computing error, and diffusing error, error diffusion requires a relatively long time to process, compared to ordered dither. An exemplary form of thresholding, termed ordered dither halftoning, shall be described herein for illustration.
Ordered dither halftoning is so named since it produces repeating, ordered rather than random, patterns of dots. The ordered patterns are objectionable relative to the random patterns produced by error diffusion. Ordered dither requires much less computation since it only employs one step of comparing an 8-bit colorant value with a threshold value.
To binarize an image, ordered dither uses threshold matrices, or two-dimensional arrays of numbers, as threshold values. For example, an 8.times.8 array of numbers on the range 0 to 255 is tiled across the logical space of a document, so that each pixel location has associated with it a threshold value. Since a threshold matrix is tiled across the page, the threshold values T repeat such that T(x, y)=T(x+8, y)=T(x, y+8) for every pixel location (x, y).
To decide whether or not to print a dot of each colorant, the 8-bit colorant values at each pixel location are compared against the corresponding threshold value. If a colorant value is greater than the threshold, a dot is printed at the pixel location, otherwise a dot is not printed. In the prior art ordered dither method, thresholding occurs independently in each dot plane according to the diagram of FIG. 2.
With ordered dither, various sized matrices such as 8.times.8 or 16.times.16 have been used. Additionally, large matrices that do not produce ordered dot patterns but are used in the same manner as described for ordered dither, and therefore have similar performance characteristics as ordered dither, have been used to halftone images.
A problem with the presently available halftoning methods is that neither error diffusion nor ordered dither produce visually pleasing patterns in a computationally efficient manner. Error diffusion produces visually pleasing patterns with significant computational expense, whereas ordered dither is computationally efficient but produces objectionable dot patterns.